Addition#
To implement add(x) in a RedBlackTree, we perform a standard BinarySearchTree insertion to add a new leaf, u, with u.x = x and set u.colour = red. Note that this does not change the black height of any node, so it
does not violate the black-height property. It may, however, violate the
left-leaning property (if u is the right child of its parent), and it may
violate the no-red-edge property (if u’s parent is red). To restore these
properties, we call the method add_fixup(u).
A single round in the process of fixing Property 2 after an insertion is illustrated in the below illustration:
1 of 5
2 of 5
3 of 5
4 of 5
5 of 5
The add_fixup(u) method takes as input a
node u whose color is red and which may violate the no-red-edge property and/or the left-leaning property. The following discussion is probably impossible to follow without referring to the above figure or recreating it on
a piece of paper. Indeed, the reader may wish to study the above figure before
continuing.
If u is the root of the tree, then we can color u black to restore both
properties. If u’s sibling is also red, then u’s parent must be black, so both
the left-leaning and no-red-edge properties already hold.
Otherwise, we first determine if u’s parent, w, violates the left-leaning
property and, if so, perform a flip_left(w) operation and set u = w. This leaves us in a well-defined state: u is the left child of its parent, w, so w now satisfies the left-leaning property. All that remains is to ensure the no-red-edge property at u. We only have to worry about the case in which
w is red, since otherwise u already satisfies the no-red-edge property.
Since we are not done yet, u is red and w is red. The no-red-edge property (which is only violated by u and not by w) implies that u’s grandparent g exists and is black. If g’s right child is red, then the left-leaning
property ensures that both g’s children are red, and a call to push_black(g)
makes g red and w black. This restores the no-red-edge property at u, but may cause it to be violated at g, so the whole process starts over with
u = g.
If g's right child is black, then a call to flip_right(g) makes w the
(black) parent of g and gives w two red children, u and g. This ensures
that u satisfies the no-red-edge property and g satisfies the left-leaning property. In this case we can stop.
The add_fixup(u) method takes constant time per iteration and each iteration either finishes or moves u closer to the root. Therefore,
the add_fixup(u) method finishes after iterations in time.
Removal#
The remove(x) operation in a RedBlackTree is the most complicated to
implement, and this is true of all known red-black tree variants. Just
like the remove(x) operation in a BinarySearchTree, this operation boils
down to finding a node w with only one child, u, and splicing w out of the
tree by having w.parent adopt u.
The problem with this is that, if w is black, then the black-height
property will now be violated at w.parent. We may avoid this problem, temporarily, by adding w.colour to u.colour. Of course, this introduces two other problems: (1) if u and w both started out black, then
u.colour + w.colour = 2 (double black), which is an invalid colour. If
w was red, then it is replaced by a black node u, which may violate the
left-leaning property at u.parent. Both of these problems can be resolved
with a call to the remove_fixup(u) method.
The remove_fixup(u) method takes as its input a node u whose colour
is black (1) or double-black (2). If u is double-black, then remove_fixup(u)
performs a series of rotations and recolouring operations that move the
double-black node up the tree until it can be eliminated. During this
process, the node u changes until, at the end of this process, u refers to
the root of the subtree that has been changed. The root of this subtree
may have changed colour. In particular, it may have gone from red to
black, so the remove_fixup(u) method finishes by checking if u's parent
violates the left-leaning property and, if so, fixing it.
The remove_fixup_case1(u) method is shown in the below illustration:
1 of 2
2 of 2
The remove_fixup_case2(u) method is shown in the below illustration:
1 of 9
2 of 9
3 of 9
4 of 9
5 of 9
6 of 9
7 of 9
8 of 9
9 of 9
The remove_fixup_case3(u) method is shown in the below illustration:
1 of 7
2 of 7
3 of 7
4 of 7
5 of 7
6 of 7
7 of 7
Again, the following text will be difficult, if not impossible, to follow without referring to the above figures. Each iteration of the loop in remove_fixup(u) processes the double-black node u, based on one of four cases:
- Case 0:
uis the root. This is the easiest case to treat. We recolouruto be black (this does not violate any of the red-black tree properties). - Case 1:
u’s sibling,v, is red. In this case,u’s sibling is the left child of its parent,w(by the left-leaning property). We perform a right-flip atwand then proceed to the next iteration. Note that this action causesw’s parent to violate the left-leaning property and the depth ofuto increase. However, it also implies that the next iteration will be in Case 3 withwcoloured red. When examining Case 3 below, we will see that the process will stop during the next iteration.
- Case 2:
u’s sibling,v, is black, anduis the left child of its parent,w. In this case, we callpull_black(w), makingublack,vred, and darkening the colour ofwto black or double-black. At this point,wdoes not satisfy the left-leaning property, so we callflip_left(w)to fix this.
At this point, w is red and v is the root of the subtree with which we
started. We need to check if w causes the no-red-edge property to be violated. We do this by inspecting w’s right child, q. If q is black, then w
satisfies the no-red-edge property and we can continue the next iteration
with u = v.
Otherwise (q is red), so both the no-red-edge property and the left-leaning properties are violated at q and w, respectively. The left-leaning property is restored with a call to rotate_left(w), but the no-red-edge
property is still violated. At this point, q is the left child of v, w is the left child of q, q and w are both red, and v is black or double-black. A flip_right(v) makes q the parent of both v and w. Following this up by a push_black(q) makes both v and w black and sets the colour of q back to the original colour of w.
At this point, the double-black node is has been eliminated and the no-red-edge and black-height properties are reestablished. Only one possible problem remains: the right child of v may be red, in which case the
left-leaning property would be violated. We check this and perform a
flip_left(v) to correct it if necessary.
- Case 3:
u’s sibling is black anduis the right child of its parent,w. This case is symmetric to Case 2 and is handled mostly the same way. The only differences come from the fact that the left-leaning property is asymmetric, so it requires different handling.
As before, we begin with a call to pull_black(w), which makes v red
and u black. A call to flip_right(w) promotes v to the root of the subtree.
At this point w is red, and the code branches two ways depending on the
colour of w’s left child, q.
If q is red, then the code finishes up exactly the same way as Case 2
does, but is even simpler since there is no danger of v not satisfying the
left-leaning property.
The more complicated case occurs when q is black. In this case, we examine the colour of v’s left child. If it is red, then v has two red children and its extra black can be pushed down with a call to push_black(v). At this point, v now has w’s original colour, and we are done.
If v’s left child is black, then v violates the left-leaning property, and
we restore this with a call to flip_left(v). We then return the node v so
that the next iteration of remove_fixup(u) then continues with u = v.
Each iteration of remove_fixup(u) takes constant time. Cases 2 and 3
either finish or move u closer to the root of the tree. Case 0 (where u
is the root) always terminates and Case 1 leads immediately to Case 3,
which also terminates. Since the height of the tree is at most , we
conclude that there are at most iterations of remove_fixup(u), so
remove_fixup(u) runs in time.
Summary#
The following theorem summarizes the performance of the RedBlackTree data structure:
Theorem 1: A RedBlackTree implements the SSet interface and supports the operations add(x), remove(x), and find(x) in worst-case time per
operation.
Not included in the above theorem is the following extra bonus:
Theorem 2: Beginning with an empty RedBlackTree, any sequence of m
add(x) and remove(x) operations results in a total of time spent during all calls add_fixup(u) and remove_fixup(u).
We only sketch a proof of Theorem 2 By comparing add_fixup(u)
and remove_fixup(u) with the algorithms for adding or removing a leaf
in a 2-4 tree, we can convince ourselves that this property is inherited
from a 2-4 tree. In particular, if we can show that the total time spent
splitting, merging, and borrowing in a 2-4 tree is , then this implies
Theorem 2.
The proof of this theorem for 2-4 trees uses the potential method of amortized analysis.
Define the potential of an internal node u in a 2-4 tree as
and the potential of a 2-4 tree as the sum of the potentials of its nodes. When a split occurs, it is because a node with four children becomes two nodes, with two and three children. This means that the overall potential drops by When a merge occurs, two nodes that used to have two children are replaced by one node with three children. The result is a drop in potential of Therefore, for every split or merge, the potential decreases by two.
Next notice that, if we ignore splitting and merging of nodes, there are only a constant number of nodes whose number of children is changed by the addition or removal of a leaf. When adding a node, one node has its number of children increase by one, increasing the potential by at most three. During the removal of a leaf, one node has its number of children decrease by one, increasing the potential by at most one, and two nodes may be involved in a borrowing operation, increasing their total potential by at most one.
To summarize, each merge and split causes the potential to drop by at least two. Ignoring merging and splitting, each addition or removal causes the potential to rise by at most three, and the potential is always non-negative. Therefore, the number of splits and merges caused by m additions or removals on an initially empty tree is at most Theorem 2 is a consequence of this analysis and the correspondence between 2-4 trees and red-black trees.
Let’s create an instance of RedBlackTree class and add values to it using the add() method.
Explanation
Let’s start our explanation from the start of main().
-
Line 146: Creates a new instance of the
RedBlackTreeclass -
The following lines add values to it in three different ways:
- Line 149–150: A sorted sequence.
- Line 157–158: A reverse sorted sequence.
- Line 165–166: A pseudorandom sequence.
It then prints out the values in the tree for each of these sequences. Finally, the tree is cleared using the clear() method.
Fundamentals of Red-Black Trees
Quiz on Red-Black Trees